`:top

Der `!Itai-Rodeh-Algorithmus`! ist ein `F33f`_`[Algorithmus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Algorithmus]`_`f der `F33f`_`[Las-Vegas Klasse`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Las-Vegas-Algorithmus]`_`f zur Auswahl anonymer `F33f`_`[unidirektionale`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Unidirektional]`_`f `F33f`_`[Ringe`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Topologie_(Rechnernetz)]`_`f und baut auf dem `F33f`_`[Chang- und Roberts-Algorithmus`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nachrichtenauslöschung_nach_Chang_und_Roberts]`_`f auf.

>>Contents

• `F0af`_`[Voraussetzungen`#voraussetzungen]`_`f

• `F0af`_`[Ablauf`#ablauf]`_`f

• `F0af`_`[Erste Phase`#erste-phase]`_`f

• `F0af`_`[Weitere Phasen`#weitere-phasen]`_`f

• `F0af`_`[Nachrichtenkomplexität`#nachrichtenkomplexit-t]`_`f

• `F0af`_`[Quellen`#quellen]`_`f

-─

>>Voraussetzungen

• unidirektionaler Ring

• Ringgröße (Anzahl der `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Netzwerkknoten]`_`f) n {\\displaystyle n} bekannt

>>Ablauf

Der Algorithmus läuft in Phasen (Wahlgängen) ab.

>>>Erste Phase

In der ersten Phase wählen alle Knoten eine zufällige `F33f`_`[Identifikationsnummer`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Identifikationsnummer]`_`f, I D > 0 {\\displaystyle \\mathrm {ID} >0} . Dann schickt jeder Knoten eine `F33f`_`[Nachricht`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nachricht]`_`f bestehend aus eigener ID i {\\displaystyle i} , Sprungzähler h {\\displaystyle h} (`*hopcount`*, gibt an, wie oft die Nachricht weitergeleitet wurde), einem Merker f {\\displaystyle f} (`*flag`*) und der aktuellen Phase p {\\displaystyle p} . Initial gilt h = 1 , f = 1 , p = 1 {\\displaystyle h=1,f=1,p=1} .

• wenn eine Nachricht ⟨ ⟨ i , h , f , p ⟩ ⟩ {\\displaystyle \\langle i,h,f,p\\rangle } empfangen wird:

• falls p {\\displaystyle p} kleiner ist als die aktuelle Phase beim Empfänger, wird die Nachricht nicht weitergeleitet („verschluckt“ nach `F33f`_`[Chang und Roberts`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Nachrichtenauslöschung_nach_Chang_und_Roberts]`_`f)

• falls i > I D {\\displaystyle i>\\mathrm {ID} } wird die Nachricht weitergeleitet als ⟨ ⟨ i , h + 1 , f , p ⟩ ⟩ {\\displaystyle \\langle i,h+1,f,p\\rangle }

• falls i < I D {\\displaystyle i<\\mathrm {ID} } wird die Nachricht nicht weitergeleitet

• falls i = I D {\\displaystyle i=\\mathrm {ID} }

• wenn h ≠ ≠ n {\\displaystyle h\\neq n} wird f {\\displaystyle f} auf 0 {\\displaystyle 0} gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als ⟨ ⟨ i , h + 1 , 0 , p ⟩ ⟩ {\\displaystyle \\langle i,h+1,0,p\\rangle } weitergeleitet

• wenn h = n {\\displaystyle h=n} und f = 1 {\\displaystyle f=1} hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)

• wenn h = n {\\displaystyle h=n} und f = 0 {\\displaystyle f=0} gibt es mehrere Gewinner.

>>>Weitere Phasen

Falls es mehrere Gewinner der ersten bzw. vorherigen Phase gibt, dann startet diese Gruppe einen weiteren Durchlauf des Algorithmus mit p = p + 1 {\\displaystyle p=p+1} . Der Ablauf ist genau wie in der ersten Phase, jedoch mit verringerter Anzahl der Teilnehmer. Passive Knoten leiten Nachrichten lediglich weiter; lediglich der Sprungzähler h {\\displaystyle h} wird dabei erhöht.

>>Nachrichtenkomplexität

Für die erste Phase werden n {\\displaystyle n} Nachrichten benötigt. Da die Anzahl der Phasen theoretisch unbegrenzt ist, geht die Nachrichtenkomplexität gegen unendlich. Praktisch ist dieser Fall aber sehr unwahrscheinlich. So kommen für jede weitere Phase weniger als n {\\displaystyle n} Nachrichten hinzu.

Der `F33f`_`[Erwartungswert`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Erwartungswert]`_`f E {\\displaystyle E} für die Anzahl der Wahlgänge (wenn ∀ ∀ I D : I D ∈ ∈ [ 1 , . . . , n ] {\\displaystyle \\forall ID:ID\\in [1,...,n]} ): E ≤ ≤ e ( n n − − 1 ) {\\displaystyle E\\leq e\\left({\\frac {n}{n-1}}\\right)} ( e {\\displaystyle e} ist die `F33f`_`[Eulersche Zahl`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Eulersche_Zahl]`_`f)

>>Quellen

• Vorlesung `*Verteilte Systeme`* an der `F33f`_`[TU-Berlin`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=TU-Berlin]`_`f

• A. Itai and M. Rodeh. Symmetry breaking in distributed networks, In `*Proceedings of the 22nd IEEE Symposium on Science`*, pages 150-158. IEEE Press, 1981.

`c`F0af`_`[↑ Back to top`#top]`_`f`a